/************************************************************************************************
 * test examples of 100 interesting program in C
 * test 047.c
 * 1~9 to form a fraction which is a natural number
 ***********************************************************************************************/

#include <stdio.h>
#include <string.h>

/*
 * this solution is only considered XXXXX/XXX form,
 * additional procedure may need for other answer
 * looking for better solutions with more efficiency
 */

#define NUMERATOR 5
#define DENOMINATOR 3

int used[9];

int formFraction(int m, int n, int pos)
{
	int flag = 0;
	// last number
	if (pos == NUMERATOR+DENOMINATOR)
	{
		int i = 0;
		for (i = 0; i < 9; i++)
			if (used[i] != 1)
			{
				int t = n*10 + (i+1);
				if (m%t == 0) 
				{
					printf("%d can be formed as %d/%d\n", m/t, m, t);
					flag += 1;
				}
			}
	}
	// form the numberator
	else if (pos <= NUMERATOR)
	{
		int i = 0;
		for (i = 0; i < 9; i++)
			if (used[i] != 1)
			{
				used[i] = 1;
				flag += formFraction(m*10+i+1, n, pos+1);
				used[i] = 0;
			}
	}
	// form the denominator
	else
	{
		int i = 0;
		for (i = 0; i < 9; i++)
			if (used[i] != 1)
			{
				// pruning
				if ((n == 0) && (used[i]*1000 > m)) break;
				else
				{
					used[i] = 1;
					flag += formFraction(m, n*10+i+1, pos+1);
					used[i] = 0;
				}
			}
	}

	return(flag);
}

int main()
{
	memset(used, 0, sizeof(int)*9);

	int count = 0;
	count = formFraction(0, 0, 1);
	printf("Total %d number(s) can be formed\n", count);
}

